typedef struct ListNode ListNode;

//反转链表函数
ListNode* reverseList(ListNode* head){
	ListNode* cur = head;
	ListNode* newhead = NULL;
	while (cur)
	{
		ListNode* next = cur->next; 
		cur->next = newhead;
		newhead = cur;
		cur = next;
	}
	
	return newhead;
}

bool isPalindrome(struct ListNode* head){
    //用快慢指针法寻找中间节点
    ListNode* slow = head;
    ListNode* fast = head;
    ListNode* prev = head;  // prev是定位链表中间节点的前一个节点
    while (fast && fast->next)
    {
        prev = slow;
        slow = slow->next;
        fast = fast->next->next;
    }

    prev->next = NULL;  // 一定要对前半部分链表的末尾置空
    slow = reverseList(slow);  // 反转后半部分的链表
	
	//同时遍历前半和后半部分的链表
    while (head)
    {
    	//判断相对应的两个节点的值是否相等
        if (head->val != slow->val)  // 如果存在不相等，则该单链表一定不是回文链表
        {
            return false;
        }

        head = head->next;
        slow = slow->next;
    }

	//能走到这里，说明该单链表必是回文链表
    return true;
}